#include<bits/stdc++.h>
using namespace std;
const int NN=2e5+4;
struct node
{
    int u,v,w;
    bool operator<(const node&it)const
    {
        return w<it.w;
    }
}edge[NN];
int fa[NN];
int find(int u)
{
    return fa[u]==u?u:fa[u]=find(fa[u]);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        vector<int>nums;
        for(int i=1;i<=m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            if(u>v)
                swap(u,v);
            nums.push_back(u);
            nums.push_back(v);
            edge[i]={u,v,w};
        }
        nums.push_back(1);
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());
        long long ans=n-nums.back();
        for(int i=0;i<nums.size()-1;i++)
            ans+=nums[i+1]-nums[i]-1;
        int cnt=0;
        set<pair<int,int> >st;
        for(int i=1;i<=m;i++)
        {
            st.insert({edge[i].u,edge[i].v});
            edge[i].u=lower_bound(nums.begin(),nums.end(),edge[i].u)-nums.begin(),edge[i].v=lower_bound(nums.begin(),nums.end(),edge[i].v)-nums.begin();
        }
        sort(edge+1,edge+1+m);
        for(int i=0;i<nums.size();i++)
            fa[i]=i;
        int cnt=nums.size(),val=0,now=1;
        while(cnt>1&&val<=n)
        {
            while(now<=m&&edge[now].w)
            {
                int fu=find(edge[now].u),fv=find(edge[now].v);
                if(fu!=fv)
                {
                    fa[fu]=fv;
                    ans+=edge[now].w;
                    cnt--;
                }
            }
            for(int i=0;i<nums.size();i++)
            {
                // if(st.count({nums[i],nums[i]+val}))
                
                
                //cnm buxiele/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu/tuu
            }
        }
        for(int i=now;i<=m;i++)
        {
            int fu=find(edge[now].u),fv=find(edge[now].v);
            if(fu!=fv)
            {
                fa[fu]=fv;
                ans+=edge[now].w;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}